#include <iostream>
#include <string>

using namespace std;

void get_next(const char * s, int * next)
{
    int i, j;

    i = 0;
    j = -1;
    next[0] = -1;

    while(i < strlen(s)-1) {
	if (j == -1 || s[i] == s[j]) {
	    ++j; ++i;
	    next[i] = j;
	}
	else
	    j = next[j];
    }
}

void get_next_v2(const char * s, int * next)
{
    int i, j;

    i = 0;
    j = -1;
    next[0]=-1;
    while (i < strlen(s)-1) {
	if (j == -1 || s[i] == s[j]) {
	    ++i; ++j;
	    if (s[i] != s[j])
		next[i] = j;
	    else
		next[i] = next[j];
	}
	else
	    j = next[j];
    }
}

// fb's phone interview question.
// replace all "%20" in text with ' ' . Bug free is required.
int replace(char * text)
{
    int occurences = 0;
    char * p = text;
    char * q = text;

    while (p && *p)
    {
        if (*p == '%' && *(p+1) == '2' && *(p+2) == '0')
        {
            *q++ = ' ';
            p += 3;
            occurences++;
        }
        else
        {
            *q++ = *p++;
        }
    }
    if (q)
        *q = '\0';

    return occurences;
}

int main(int argc, char ** argv)
{
#if 0
    char * str;
    //string str("Hello, world. I'm in Beijing now.\n");
    //str = "abaabcac";
    if (argc < 2) {
	fprintf (stderr, "Usage: str patternstring\n");
	return -1;
    }

    str = argv[1];
    int len = strlen(str);
    int * next = new int[len];

    get_next(str, next);
    cout << str << '\n';
    for (int i = 0; i < len; i++)
	cout << next[i];
    cout << endl;

    get_next_v2(str, next);
    for (int i = 0; i < len; i++)
	cout << next[i];
    cout << endl;

    delete [] next;
#endif

    char * text = argv[1];
    cout << "text=\"" << text << "\"" << endl;

    int occurences = replace(text);

    cout << "occurences=" << occurences << " replaced_text=" << text << endl;
}
